package sort.algorithm;

import sort.record.Record;
import sort.record.Records;

/**
 * @author masaru-gotou
 *
 */
public class QuickSort extends Sorter {
	/* (�� Javadoc)
	 * @see sort.Sorter#sort(sort.Records)
	 */
	@Override
	public Records sort(Records records) {
//		return sort(records,0,records.size()-1);
		return quickSort(records,0,records.size()-1);
	}
	/**
	 * �N�C�b�N�\�[�g�i�ċA�p�j
	 * �^����ꂽrecords�́Alo����hi�܂ł��\�[�g���܂��B
	 * http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html
	 * @param records
	 * @param lo
	 * @param hi
	 * @return
	 */
	private Records quickSort(Records records, int lo, int hi) {
		if ( lo == hi ) return records;
		Record pivot_record = getPivot(records,lo,hi);	// �s�{�b�g��ݒ�
		if ( pivot_record != null ) {	// �s�{�b�g�����������Ƃ������\�[�g
			// �p�[�e�B�V��������
			int partitioned_index = partition(records, lo, hi, pivot_record.getKey());
			// ���������������\�[�g
			quickSort(records, lo, partitioned_index-1);
			// ���������E�����\�[�g
			quickSort(records, partitioned_index, hi);
		}
		return records;
	}
	/**
	 * �p�[�e�B�V��������
	 * recors.get(i)�`records.get(j)�̊ԂŁApivot �����Ƃ��ĕ������܂��B
	 * pivot ��菬�����v�f�͑O�ɁA�傫���v�f�͂�����ɗ��܂��B
	 * �傫���v�f�̊J�n�ԍ���Ԃ��܂��B
	 * 
	 * @param records
	 * @param lo
	 * @param hi
	 * @param pivot
	 * @return
	 */
	private int partition(Records records, int lo, int hi, int pivot) {
		int l=lo;	// ������̌����J�n�ʒu
		int r=hi;	// �E����̌����J�n�ʒu
		
	    // ��������������܂ŌJ��Ԃ��܂�
	    while(l<=r){
			// ������A���v�f�ȏ�̃f�[�^��T���܂�
			while(l<=hi && records.get(l).getKey()<pivot)  l++;
			
			// �E����A���v�f�����̃f�[�^��T���܂�
			while(r>=lo && records.get(r).getKey()>=pivot) r--;
			
			if(l>r) break;	// ���������甲����
			
			// ������������ւ���
			Record tmp = new Record(records.get(l));
			records.set(l, records.get(r));
			records.set(r, tmp);
			setChanged();
			notifyObservers(records);
			
			l++; r--;
	    }
		
		return l;
	}
	/**
	 * �s�{�b�g�l�i���v�f�j�̎擾
	 * ���v�f�ƂȂ�record�I�u�W�F�N�g��Ԃ��܂��B
	 * �s�{�b�g�̑I�����W�b�N��
	 * �@���Ɍ��āA�ŏ��Ɍ��������قȂ�Q�̗v�f�̂����A�傫���ق���record��Ԃ��܂��B
	 * �@�S�������v�f�̏ꍇ��null��Ԃ��܂��B
	 * @param records
	 * @param lo
	 * @param hi
	 * @return ���v�f�ƂȂ�record�I�u�W�F�N�g
	 */
	private Record getPivot(Records records, int lo, int hi) {
		int k = lo + 1;	// ������2�Ԗڂ̗v�f�ԍ�
		
		// �Ō�̗v�f�܂ł𒲂ׁA������1�Ԗڂ̗v�f�ƈقȂ�v�f��T��
		for ( ; k<=hi; k++ ) {
			if ( records.get(lo).getKey()!=records.get(k).getKey() ) break;
		}
		if ( k > hi ) return null;	// �قȂ�v�f�������ꍇ��null
		// �傫���ق���Ԃ�
		if ( records.get(lo).getKey() >= records.get(k).getKey() ) {
			return records.get(lo);	
		}
		return records.get(k);
	}
	@Override
	public String getName() {
		return "Quick Sort";
	}
}
